#include <bits/stdc++.h>

using namespace std;

// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
private:
    static const int MAXN = 3001;
    TreeNode* nq[MAXN];
    unsigned int iq[MAXN];
    int l, r;

public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        unsigned int ans = 1;
        l = r = 0;
        nq[r] = root;
        iq[r++] = 1;
        while(l < r)
        {
            int size = r - l;
            ans = max(ans, iq[r - 1] - iq[l] + 1);
            for(int i = 0; i < size; ++i)
            {
                TreeNode* cur = nq[l];
                unsigned int id = iq[l++];
                if(cur->left)
                {
                    nq[r] = cur->left;
                    iq[r++] = 2 * id;
                }
                if(cur->right)
                {
                    nq[r] = cur->right;
                    iq[r++] = 2 * id + 1;
                }
            }
        }

        return ans;
    }
};